BZOJ2201 彩色圆环 <概率DP>

Problem

彩色圆环

Description

Input

仅有一行，该行给出依次两个正整数，分别表示宝石的个数和宝石在变化时可能变成的颜色种类数。

Output

应仅有一行，该行给出一个实数，表示圆环的“美观程度”的期望值。

Sample Input

8 1

Sample Output

8.00000

HINT

的数据满足，。

标签：概率DP

Solution

考虑用期望。用表示颗珠子，首尾颜色相同/不相同的期望美观程度。枚举最后一节相同颜色珠子的长度进行转移。需要先预处理表示连续颗珠子颜色相同的概率。

边界：
状态转移：
答案：

对于状态转移的部分，上式中是新加入的一串颜色不能和原来的首和尾颜色相同，是新加入的一串颜色不能和原来的首和尾相同，而原来的首和尾同色；下式中是新加入的一串颜色必须和原来的首相同。
对于统计答案的部分，枚举的代表首所在的颜色连续段的长度为，这样的串有种，每种的这个部分贡献为，剩下部分期望贡献为。
时间复杂度。

Code

#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; dnt m, ans;
dnt p[205], f[205][2];
int main() {
    read(n), read(m);
    m = 1.0/m, p[1] = 1, f[1][1] = 1;
    for (int i = 2; i <= n; i++) p[i] = p[i-1]*m;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            f[i][0] += f[i-j][0]*p[j]*j*(1-2*m), 
            f[i][0] += f[i-j][1]*p[j]*j*(1-m), 
            f[i][1] += f[i-j][0]*p[j]*j*m;
    for (int i = 1; i < n; i++)
        ans += f[n-i+1][0]*p[i]*i*i;
    ans += p[n]*n;
    return printf("%.5lf\n", ans), 0;
}